539. Жители
Катана
В стране имеются города
(вершины графа) и дороги (ребра графа) длины 1. Необходимо найти длину самого
длинного пути. Ни одно ребро в пути не может быть использовано дважды. Но при
этом разрешается проходить несколько раз по одному городу.
Вход. Содержит несколько тестов. Первая строка каждого
теста содержит количество вершин n (2
£ n £ 25) и ребер m
(1 £ m £ 25) графа. Следующие m строк описывают неориентированные ребра графа. Вершины
пронумерованы от 0 до n – 1. Степень
каждой вершины не более 3. Граф не обязательно связный. Последний тест содержит
n = m = 0 и не обрабатывается.
Выход. Для
каждого теста в отдельной строке вывести длину наибольшего пути.
3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0
212
бектрекинг
Запускаем алгоритм построения
всех путей из каждой вершины графа, используя бектрекинг. В оптимальное время
нам позволяют уложиться ограничения. Длину наибольшего пути запоминаем в
переменной best.
Матрицу смежности графа
храним в массиве mas.
#define MAX 26
int
mas[MAX][MAX];
Основной цикл программы.
Читаем данные графа в матрицу смежности mas. Запускаем поиск всех путей,
начинающихся в вершине i вызовом
функции run(i, 0). Второй аргумент
функции run содержит текущую длину построенного пути.
while(scanf("%d
%d",&n,&m),n+m)
{
memset(mas,0,sizeof(mas));
for(i = 0; i < m; i++)
scanf("%d %d",&a,&b),mas[a][b] =
mas[b][a] = 1;
for(best = i = 0; i < n; i++)
run(i,0);
printf("%d\n",best);
}
Функция run(i, depth)
совершает поиск путей из вершины i
методом бектрекинга:
1. Если существует ребро (i, j),
то запускаем функцию run(j, depth + 1), увеличивая пройденный путь
на 1. При этом ребро (i, j) удаляем из рассмотрения. Когда при
помощи бектрекинга снова вернемся в вершину i,
то добавим ребро (i, j).
2. Если ни для какого j не существует ребра (i, j),
то возвращаемся в вершину, из которой мы попали в i.
void run(int
i,int depth)
{
int j;
if (depth > best) best = depth;
for(j = 0; j < n; j++)
if (mas[i][j])
{
mas[i][j] =
mas[j][i] = 0;
run(j,depth+1);
mas[i][j] =
mas[j][i] = 1;
}
}
При каждом вызове функции
run сравниваем depth со значением best. Если на текущем шаге построен
путь, длина которого больше best, то
устанавливаем best = depth.